#include "../head/listHelper.cpp"

/**
 * 206 : 循环方式反转链表
 * 时间复杂度 O(n)
   空间复杂度 O(1)
 * pre初始执行null  cur指向当前指针  next指向下一个,
 * cur指向节点指向下一个元素指针指向pre指针 
 *	 pre指向当前指针   cur 指向当前next指针 next 通过自身的下一个元素指向下一个元素
 *
 */
class ReverseLinkedList{
public:
    ListNode* reverseList(ListNode* head) {
		
        ListNode* pre = NULL;	// 指向之前元素的指针
		ListNode* cur = head;   // 当前处理的节点 
	    while(cur != NULL){
			ListNode* next = cur->next; // 指向cur 指向的next节点
			// 先把cur指向next指针指向pre指向节点
			cur->next = pre;
			// pre 指向当前指针指向节点
			pre = cur;
			// 当前指针指向next 指针指向节点
			cur = next;
		}
		return pre;		// cur 指向的是空指针  pre指向的是当前链表的头结点
    }
};


int main(){
	int arr[] = {1,2,3,4,5};
	int n = sizeof(arr)/sizeof(int);
	ListNode*  head = createLinkedList(arr, n);
	printLinkedList(head);
	
	ListNode* head2 = ReverseLinkedList().reverseList(head);
	printLinkedList(head2);
	deleteLinkedList(head2);
}
